The structure of a typical telephone number may generally include an access code, a country code, an area code, and a local number. Depending on the type of call, whether intercontinental, country to country, region to region, area to area, or even local, all the digits making up a telephone number may or may not be required to be dialed, depending on the particular telephone dial plan of each specific country. Special services such as police, emergency medical help, fire department, information services, and the like may have their own particular sets of digits that must be dialed to access such services.
A telephone dial plan, hereinafter referred to as a dial plan, is a plan which defines the expected number of digits to be dialed for a telephone number and the pattern of digits required when dialing the telephone number. The dial plan, generally based on a telephone number plan, includes the access codes, country codes, area codes and all combinations of digits which may be dialed when dialing a telephone number. In a telephone numbering plan, telephone number ranges are allocated to countries, regions, areas and local exchanges, to mobile phone networks, and to special services such as the police or public information services among others.
An access code is that part of a telephone number dialed only when dialing international and national (non-local domestic) calls, and is often used as if it were part of the telephone number. Typically, the most common national access code is “0”, and the most common international access code “00”, although in the United States and Canada, “1” and “011” are used, respectively.
A country code is that part of the telephone number dialed only when dialing to telephones in other countries. It is often used together with an international access code which must precede it in the dial string.
An area code is that part of a telephone number dialed from outside the code area and generally also from mobile phones. Area codes generally refer to geographical areas within one country that are covered by perhaps hundreds of telephone exchanges, including Private Branch Exchanges (PBX) and Private Automatic Branch Exchanges (PABX), all of which may also be referred to hereinafter as a telephone switch or a gateway, and are usually preceded in the dial string by either the national access code or the international access code and country code depending on the origin of the call.
A local number is that part of the telephone number identifying the final destination of a telephone call and must always be dialed in its entirety. The first few digits in the local number typically indicate smaller geographical areas or individual telephone exchanges. In mobile networks they generally indicate the original network provider. When calling from a telephone number in a given area or country code to another telephone in the same given area or country code usually, it is sufficient just to dial the local telephone number so that shorter dial strings are used.
As the numbers of telephones grow worldwide, there is an increasing demand for a telephone numbering plan which standardizes the various access codes, area codes and special services available in every region. Generally, the area codes are used to partition groups of subscribers within a certain area, and access codes are used to allow routing a call to a specific destination. International dialing complicates the scheme further—every country handles this issue differently; in the USA, for instance, federal regulations specify exactly how many digits there are in an area code and in a phone number—and in some Asian countries regulation is rather permissive Phone numbers can be as short as 1 digit and as long as 30 or more digits, depending on the network location of the caller.
The International Telecommunications Union (ITU), based in Geneva, Switzerland, is an international organization established in an effort to standardize and regulate international radio and telecommunications. Its main tasks are to promote and develop standardization, allocation of the radio spectrum, and organizing interconnection arrangements between different countries to allow international phone calls. The ITU is responsible for issuing recommendations which essentially serve as standards to be adopted by all countries participating in the ITU, although in reality the countries are not required to adopt the recommendations.
Although the ITU has attempted to promote common standards among the participating countries, telephone numbering plans take different formats in different parts of the world. For example, the ITU recommends that member states adopt “00” as their international access code, however, the United States, Canada, and other countries and territories participating in the North American Numbering Plan (NANP) have not accepted this format. The ITU international telephone numbering plan, through the E.164 standard, regulates country codes at the international level and sets a maximum length limit on a full international phone number. However, each country is responsible for defining the numbering system within its own network. As a result, regional area codes may have a fixed length (for example, 3 digits in the United States and Canada; 1 digit in Australia) or may have a variable length (for example, between 2 and 5 in Germany and in Austria; between 1 and 3 in Japan; 1 or 2 in Israel), or may even be incorporated into the subscriber's number, as is the case in many countries, such as Spain or Norway (for example, a local number in Madrid includes “91” which is also the area code). In some cases a trunk code, typically “0”, must still be dialed, as in Belgium, Italy, Poland, Sweden, Switzerland and South Africa.
A closed telephone numbering plan is one in which the subscriber's number is a standard length, and is used for all calls, even in the same area. Such a plan, for example as may be found in North America, includes fixed length area codes and fixed length local numbers. An open telephone numbering plan, still visible in many countries which have not adopted any standardization procedures, typically includes variable length area codes and/or local numbers.
An open dialing plan is one in which there are different dialing arrangements for local and for long distance telephone calls. For local calls, identified by those telephone numbers containing the same area code, callers need only dial the number, but for calls outside the area, identified by those telephone numbers having a different area code, dialing of the area code is required. The area code is generally prefixed by a trunk code (usually “0”), which is usually omitted when calling from outside the country.
To call a number in Amsterdam in the Netherlands for example:
xxx xxxx(within Amsterdam - no area code required)(020) xxx xxxx(outside Amsterdam)+31 20 xxx xxxx(outside the Netherlands)In the United States, Canada, and other countries or territories using the North American Numbering Plan (NANP), the trunk code is ‘1’, which is also (by coincidence) the country calling code. To call a number in San Francisco, the dialing procedure will vary:
xxx xxxx(local calls, no area code required)1 415 xxx xxxx(outside San Francisco)415 xxx xxxx(mobile phones within NANP)+1 415 xxx xxxx(calls from outside NANP)However, in parts of North America, where a new area code overlays an older area code, dialing 1+area code is now required even for local calls, which means that the NANP is now closed in certain areas and open in others. Dialing from mobile phones is different in that the trunk code is not necessary.
A closed dialing plan is one in which the subscriber's number is used for all calls, such that the area code is integrated as part of the telephone number even if the call is local. The emphasis nowadays, in a closed dialing plan, is to make all numbers a standard length, and incorporate the area code into the subscriber's number. This usually makes the use of a trunk code unnecessary. For example, to call Oslo in Norway before 1992, one would dial (open dialing plan):
xxx xxx(within Oslo - no area code required)(02) xxx xxx(within Norway - outside Oslo)+47 2 xxx xxx(outside Norway)After 1992, this changed to a closed eight-digit numbering plan (closed dialing plan):
22xx xxxx(within Norway - including Oslo)+47 22xx xxxx(outside Norway)In other countries, such as France, Belgium, Switzerland, and South Africa, the trunk code is retained for domestic calls, whether local or national:
Paris 01 xx xx xx xx (outside France +33 1 xx xx xx xx)
Telephone exchanges, or switches, make routing decisions of voice and/or data based on the dialed telephone number. A phone call will typically go through several switches before reaching its destination, and a typical switch normally handles thousands of dialing attempts concurrently. Communication between switches is performed using various standard protocols, such as Channel-Associated-Signaling (CAS), or Common Channel Signaling (CCS), which includes Signaling System #7 (SS7) and Integrated Services Digital Network (ISDN), or two-wire analog telephone lines; each of these protocols specifies a different method for transmitting the dialed number from one switch to the next.
Channel Associated Signaling (CAS) is a form of digital communications signaling. As with most telecommunication signaling methods, it uses routing information to direct the voice and/or data to its destination. With CAS signaling, this routing information is encoded and transmitted in the same channel as the voice and/or data. This information can be transmitted in the same band (in-band signaling) or a separate band (out-of-band signaling) to the voice and/or data.
In-band signaling is the sending of control signals, including routing information, over the same channel as which the voice and/or data is being transmitted. Out-of-band signaling is the sending of control signals, including routing information, on a separate channel to that (or those) through which the voice and/or data is being transmitted. Out-of-band signaling is the signaling method used for ccS.
Signaling System #7 (SS7) is a standardized telephone communications protocol used to set up all the telephone calls among all the world's telephone networks, better known as the public switched telephone network (PSTN). SS7 provides a common structure for telephone network signaling, messaging, interfacing, and network maintenance. It deals with establishment of a call, exchanging user information, call routing, different billing structures, and supports other varied telecommunications services, including linking VoIP (voice-over-internet protocol) to the PSTN and in mobile phone voice and data applications.
Integrated Services Digital Network (ISDN) is a circuit-switched telephone network system whereby digital transmission of voice and data can be simultaneously done over a regular telephone line at a greater speed and better quality compared to analog transmission. ISDN specifically defines a set of protocols for establishing and breaking circuit switched connections over the PSTN, and for providing advanced call features for the user, including voice, fax, data and video capabilities.
Many of the protocols used in the PSTN, particularly those associated with CAS, with transmission over analog telephone lines, with VoIP, and others, do not necessarily mandate a method for detecting the end of the dial string. Digits are transmitted sequentially and the receiving switch must collect them, identify the phone number, and make the appropriate routing decision. Since it is not possible to tell the length of the dialed phone number, every switch employs a dialing time-out and processes the dialed number after a pause in dialing which may last up to several seconds. The following is a general description of the scenario by which a telephone call between two parties advances along the PSTN network:    a. A caller will pick up the telephone and will dial the telephone number of the receiver. If the receiver is in another area code usually the area code of the receiver will be dialed together with the local number. If the receiver is in another country then the country code will be added also and maybe some access code will also be required, particularly if going to another continent.    b. The call will usually first be transferred to a local telephone exchange in the same area as the caller. After a timeout period which indicates the end of the dial string the call will be transferred to a regional telephone exchange where, after another timeout period to determine the end of the dial string, the call may be transferred to a national telephone exchange (if going to another country).    c. After an additional timeout at the national telephone exchange to verify end of dial string the call is transferred to a continental telephone exchange if the call is going outside the continent, where there is an additional timeout to verify end of dial string.    d. The call is then transferred to the receiving continental telephone exchange where there is another timeout to verify the end of the dial string, and subsequently transferred in an inverse manner down to the receiving national telephone exchange, receiving regional telephone exchange and receiving local telephone exchange, and finally to the receiver, all with the respective timeouts required to detect the end of the dial string at each exchange.When the call is routed through several switches, the timeouts accumulate to form slow end-to-end response times. This problem may cause revenue loss to telephone carriers forcing them to adopt corrective measures in an effort to minimize losses.
As a possible corrective measure for the accumulated timeout most telephone carriers are able to produce a rule-database consisting of the possible number patterns required by the numerous telephone numbering plans available worldwide covering the different countries. Some switches can be configured with this database, however traversing this database and comparing the digits dialed by the caller is a difficult task which consumes large amounts of memory and processing resources. Conceptually, it is possible to program the gateway in question with all possible area codes and phone number lengths. This requires that the switching equipment supplier supply a preconfigured gateway to the carrier company equipped with all the necessary equipment and infrastructure as may be required to identify all possible phone numbers. The main disadvantage of this approach is cost and maintenance—since telephone numbering plans and dial plans change with time, the equipment supplier needs to constantly replace the gateway or parts of it; which is usually not satisfactorily accepted by a telephone carrier.
U.S. Pat. No. 6,167,126, “Method for Flexibly Provisioning Switching Devices and a Switching Device Incorporating the Same”, the disclosure of which is incorporated herein by reference in its entirety, describes a programming language which allows field-programming of the dial plan.
ITU-T Recommendation H.248.1 “Gateway Control Protocol”, which is incorporated herein by reference in its entirety, describes a DigitMap descriptor as “a dialing plan resident in the Media Gateway used for detecting and reporting digit events received on a Termination.”
D. E. Knuth, J. Morris and V. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing, 6, 1977, which is incorporated herein by reference in its entirety, especially at pages 189-195, describes a method by which the KMP string searching algorithm is used for comparing incoming digit streams with a predefined finite state-machine.
A finite state machine is a model of behavior extensively used in computer science, mathematics, electrical engineering, logic, psychology and other specialized fields. The model is essentially composed of states (including an initial state), input events, output events, and transition functions. A state, which can also be referred to as a current state, stores information about the past so that it reflects the input changes from the system start to the present moment. A transition function then takes the current state and an input event, or a series of input events, and returns a new set of output events and a next state, which in turn are acted upon by a new transition function generating a new set of output events and a new “next” state, the sequence continuously repeated until a single final or a series of final terminating states are achieved.
A review of the existing methods used to manipulate dial plans in gateways shows that their implementation can be cumbersome and expensive, requiring in many cases extensive computing resources and infrastructure. Therefore, there is a requirement for a method to manipulate dial plans requiring limited computing resources while providing fast accurate pattern-matching capabilities, and for a system by which to implement the method.
The foregoing examples of the related art and limitations related therewith are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent to those of skill of the art upon a reading of the specification and a study of the figures.